import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/14 20:34
 * @description 由于 n = 10^9 , 硬模拟肯定会TLE，而 灯 和 查询 数据范围只有 2* 10^5, 因此，可以使用hashMap来标记行，列，对角线的灯，这样可以在O(1)时间内
 * 处理所有的 lamps[i]，查询后要进行灭灯操作，因此还需要记录灯的位置，然后进行对应的
 */
public class Solution {
    public static void main(String[] args) {

    }
    int[][] dirs = new int[][]{{0,0},{0,-1},{0,1},{-1,0},{-1,-1},{-1,1},{1,0},{1,-1},{1,1}};
    public int[] gridIllumination(int n, int[][] lamps, int[][] queries) {
        long N = n;
        // 记录灯照亮的位置
        Map<Integer, Integer> row = new HashMap<>(), col = new HashMap<>();
        Map<Integer, Integer> left = new HashMap<>(), right = new HashMap<>();
        // 记录灯的位置，二维转一维，x * n + y
        Set<Long> set = new HashSet<>();
        for (int[] l: lamps) {
            int x = l[0], y = l[1];
            int a = x + y, b = x - y;
            // 避免加入重复的灯
            if (set.contains(x * N + y)) {
                continue;
            }
            increment(row, x); increment(col, y);
            increment(left, a); increment(right, b);
            set.add(x * N + y);
        }
        int m = queries.length;
        int[] ans = new int[m];
        for (int i = 0; i < m; i++) {
            int[] q = queries[i];
            int x = q[0], y = q[1];
            int a = x + y, b = x -y ;
            if (row.containsKey(x) || col.containsKey(y) || left.containsKey(a) || right.containsKey(b)) {
                ans[i] = 1;
            }
            // 周围八个方向查询是否有灯，有则关掉，并且减少这个灯的影响
            for (int[] d: dirs) {
                int nx = x + d[0], ny = y + d[1];
                int na = nx + ny, nb = nx - ny;
                if (nx < 0 || nx >= n || ny < 0 || ny >= n) {
                    continue;
                }
                if (set.contains(nx * N + ny)) {
                    set.remove(nx * N + ny);
                    decrement(row, nx); decrement(col, ny);
                    decrement(left, na); decrement(right, nb);
                }
            }
        }
        return ans;
    }

    /**
     * 某个位置的灯亮着，那么行，列，对角线的位置都能照亮，那么 + 1
     * @param map map
     * @param key key
     */
    public void increment(Map<Integer, Integer> map, int key) {
        map.put(key, map.getOrDefault(key, 0) + 1);
    }

    /**
     * 某个位置的灯灭了，那么行，列，对角线的位置需要减少一次，如果刚好只有一盏灯找亮，那么灭灯后，该位置无法照亮
     * @param map map
     * @param key key
     */
    public void decrement(Map<Integer, Integer> map, int key) {
        if (map.get(key) == 1) {
            map.remove(key);
        }else {
            map.put(key, map.get(key) - 1);
        }
    }
}
